using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace EasyPath_CSharp
{

    class TwoValue<V>
    {
        public TwoValue(){}

        public TwoValue(V leftValue, V rightValue)
        {
            this.leftValue = leftValue;
            this.rightValue = rightValue;
        }

        public V leftValue { get; set; }

        public V rightValue { get; set; }


    }

    class DiffTwoValue<V>: TwoValue<V>
    {
        public DiffTwoValue()
        {
            times = 0;
        }

        public int times { get; set; }
    }

    class DictionaryDiff<K, V>
    {

        public DictionaryDiff(
            IDictionary<K, V> leftOnly,
            IDictionary<K, V> rightOnly,
            IDictionary<K, V> both,
            IDictionary<K, TwoValue<V>> merge
            )
        {
            this.leftOnly = leftOnly;
            this.rightOnly = rightOnly;
            this.both = both;
            this.merge = merge;
        }

        public IDictionary<K, V> leftOnly { get; set; }

        public IDictionary<K, V> rightOnly { get; set; }

        public IDictionary<K, V> both { get; set; }

        public IDictionary<K, TwoValue<V>> merge { get; set; }
    }

    class DictionaryUtils
    {

        public static DictionaryDiff<K, V> diff<K, V>(IDictionary<K, V> left, IDictionary<K, V> right)
        {

            var diffDict = new Dictionary<K, DiffTwoValue<V>>(left.Count);

            foreach (KeyValuePair<K, V> pair in left)
            {
                DiffTwoValue<V> v = null;
                diffDict.TryGetValue(pair.Key, out v);
                if(v == null)
                {
                    v = new DiffTwoValue<V>();
                    diffDict.Add(pair.Key, v);
                }
                v.leftValue = pair.Value;
                v.times--;
            }

            foreach (var pair in right)
            {
                DiffTwoValue<V> v = null;
                diffDict.TryGetValue(pair.Key, out v);
                if (v == null)
                {
                    v = new DiffTwoValue<V>();
                    diffDict.Add(pair.Key, v);
                }
                v.rightValue = pair.Value;
                v.times++;
            }

            var leftOnly = new Dictionary<K, V>();
            var rightOnly = new Dictionary<K, V>();
            var both = new Dictionary<K, V>();
            var merge = new Dictionary<K, TwoValue<V>>();

            foreach(var kv in diffDict)
            {
                var v = kv.Value;
                var key = kv.Key;

                var leftValue = v.leftValue;
                var rightValue = v.rightValue;

                switch (v.times)
                {
                    case -1:
                        leftOnly.Add(key, leftValue);
                        break;

                    case 1:
                        rightOnly.Add(key, rightValue);
                        break;

                    case 0:
                        if(leftValue.Equals(rightValue))
                        {
                            both.Add(key, leftValue);
                        }else
                        {
                            merge.Add(key, new TwoValue<V>(leftValue, rightValue));
                        }
                        break;
                }
            }

            return new DictionaryDiff<K, V>(leftOnly, rightOnly, both, merge);
        }
    }
}
